Ecient Algorithms for the All Pairs Shortest Path Problem with Limited Edge Costs

Takaoka T.

In this paper we deal with a directed graph G = (V; E) with non-negative integer edge costs where the edge costs are bounded by c and /V/ = n and m = /E/. We show the all pairs shortest path (APSP) problem can be solved in O (mn+n2 log (c/n))) time with the data structure of cascading bucket system. The idea for speed-up is to share a single priority queue among n single source shortest path (SSSP) problems that are solved for APSP. We use the traditional computational model such that comparison-addition operations on distance data and random access with O (log n) bits can be done in O (1) time. Also the graph is not separated, meaning m��n. Our complexity is best for a relatively large bound on edge cost, c, such that c = o (n log n).

Cite as: Takaoka T. (2012). Ecient Algorithms for the All Pairs Shortest Path Problem with Limited Edge Costs. In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 21-26

(from crpit.com) (local if available)